package com.njupt.DynamicProgramming;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: wujiaming
 * @CreateTime: 2025/2/15 22:21
 * @Description: 279. 完全平方数
 * @Version: 1.0
 */


public class NumSquares_279 {

    public int numSquares(int n) {
        List<Integer> nums = new ArrayList<>();
        isValid(nums,n);
        int[] dp = new int[n+1];
        dp[0] = 0;
        for (int i = 1; i < dp.length; i++) {
            dp[i] = Integer.MAX_VALUE;
        }

        for (int i = 0; i < nums.size(); i++) { //遍历背包
            for (int j = nums.get(i); j <= n ; j++) {
                if(dp[j - nums.get(i)] != Integer.MAX_VALUE){
                    dp[j] = Math.min(dp[j],dp[j - nums.get(i)] + 1);
                }

            }
        }

        return dp[n];
    }

    private void isValid(List<Integer> nums, int n) {

        for (int i = 1; i <=n ; i++) {
            for (int j = 1; j <= Math.sqrt(i) ; j++) {
                if(j * j == i){
                    nums.add(i);
                    break;
                }
            }
        }
    }

    public static void main(String[] args) {
        NumSquares_279 test = new NumSquares_279();
        int result = test.numSquares(13);
        System.out.println(result);
    }
}
